package com.atguigu.sort;

import java.util.Arrays;

/**
 * @author RuiKnag
 * @create 2021-05-23-16:14
 * 将所有的数字统一为同样长度的，数位较短的前面数字补0，然后从低位开始，依次进行依次排序。这样从最低为开始排序一直到最高位完成以后，数列就变成了一个有序数列
 */
public class RadixSort {
    //求出最大数字的长度
    static int finMaxNumLen(int[] arr){
        int max_num=arr[0];
        for (int i = 1; i < arr.length; i++) {
            if(arr[i]>max_num){
                max_num=arr[i];
            }
        }
        return max_num+"".length();
    }
    static void sort(int[] arr){
        //确定我们的数字的最大长度，建立一个数组
        int[] count=new int[10];
        int[] res=new int[arr.length];
        for (int i = 0; i < finMaxNumLen(arr); i++) {
            int division=(int)Math.pow(10,i);
            //我们求出对应位数的值的数量
            for (int j = 0; j < arr.length; j++) {
                int num=arr[j]/division%10;
                count[num]++;
            }
            //进行一个累加,确定对应的数最后一个位置
            for (int j = 1; j < count.length; j++) {
                count[j]+=count[j-1];
            }
            //将结果放到结果的数组中
            for (int j = res.length-1; j >=0 ; j--) {
                int num=arr[j]/division%10;
                res[--count[num]]=arr[j];
            }
            //将每一轮的结果复制到原数组中
            System.arraycopy(res,0,arr,0,arr.length);
            //清空计数数组
            Arrays.fill(count,0);

        }
    }


}
